package com.zhugang.week13.slidingwindow;


import java.util.HashMap;
import java.util.Map;

/**
 * @program algorithms
 * @description: minWindow
 * @author: chanzhugang
 * @create: 2022/09/19 19:02
 */
public class MinWindow {

    /**
     * 76 最小覆盖子串
     * https://leetcode.cn/problems/minimum-window-substring/
     *
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        // s中涵盖t最小子串， 连续子串问题，想到滑动窗口

        // 涵盖？ map 比较
        // [l, r] r向右滑动，是否涵盖， ++
        Map<Character, Integer> tmap = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            updateMap(tmap, t.charAt(i), 1);
        }


        int minSize = Integer.MAX_VALUE;
        // 起始-终止位置，字符串截取用
        int minL = -1;
        int minR = -1;

        int l = 0;
        int r = -1;
        int n = s.length();
        Map<Character, Integer> smap = new HashMap<>();
        while (l < n && r < n) {
            if (!cover(smap, tmap)) {
                // 没有覆盖,r++
                r++;
                if (r > n - 1) {
                    break;
                }
                updateMap(smap, s.charAt(r), 1);
            } else {
                // 覆盖了, l++
                if (minSize > r - l + 1) {
                    minSize = r - l + 1;
                    minL = l;
                    minR = r;
                }
                updateMap(smap, s.charAt(l), -1);
                l++;
            }
        }
        if (minL == -1) {
            return "";
        }
        return s.substring(minL, minR + 1);
    }

    /**
     * 是否覆盖： tmap的key 在smap 中存在，且 value <= smap中的value
     *
     * @param smap
     * @param tmap
     * @return
     */
    private boolean cover(Map<Character, Integer> smap, Map<Character, Integer> tmap) {
        for (Map.Entry<Character, Integer> entry : tmap.entrySet()) {
            Character key = entry.getKey();
            if (!smap.containsKey(key)) {
                return false;
            }
            if (smap.get(key) < entry.getValue()) {
                return false;
            }
        }
        return true;
    }

    private void updateMap(Map<Character, Integer> map, char c, int count) {
        if (map.containsKey(c)) {
            count += map.get(c);
        }
        map.put(c, count);
    }
}